//https://leetcode.cn/problems/maximum-subarray/description/

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& array) {
        // write code here
        if (array.empty()) return 0;
        int max_res = INT_MIN;
        int last_sum = 0;
        for(size_t i=0;i<array.size();++i) {
            if(last_sum >=0) {
                last_sum = last_sum + array[i];
            }else {
                last_sum = array[i];
            }
            max_res = std::max(last_sum,max_res);
        }
        return max_res;

    }
};